package com.sali.BFS;

import javafx.util.Pair;

import java.util.*;

/**
 * @author sali
 * @date 2025/5/2 14:54
 */
public class LeetCode_314 {

    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        Queue<Pair<TreeNode, Integer>> myQue = new ArrayDeque<>();
        myQue.offer(new Pair(root, 0));
        Map<Integer, List<Integer>> columnTable = new HashMap<>();
        while (!myQue.isEmpty()) {
            int size = myQue.size();
            for (int i = 0; i < size; i++) {
                Pair<TreeNode, Integer> myPair = myQue.poll();
                TreeNode curNode = myPair.getKey();
                Integer curVal = myPair.getValue();
                if (columnTable.get(curVal) == null) {
                    List<Integer> curList = new ArrayList<>();
                    curList.add(curNode.val);
                    columnTable.put(curVal, curList);
                } else {
                    columnTable.get(curVal).add(curNode.val);
                }

                if (curNode.left != null) {
                    myQue.offer(new Pair(curNode.left, curVal - 1));
                }
                if (curNode.right != null) {
                    myQue.offer(new Pair(curNode.right, curVal + 1));
                }
            }
        }
        List<Integer> sortList = new ArrayList<>(columnTable.keySet());
        Collections.sort(sortList);
        for (Integer sort : sortList) {
            res.add(columnTable.get(sort));
        }
        return res;
    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}